#include <iostream>
using namespace std;
// 链表节点的定义
template <typename T> class Link
{
protected:
    T data;//节点的内容
    Link<T> * next;//指向后一节点的指针
public:
    Link(const T info,const Link<T> * nextValue = NULL)
    {
        data = info;
        next = nextValue;
    }
    Link(const Link<T>* nextValue)
    {
        next = nextValue;
    }
};
// 单链表的定义
template <typename T>
class lnkList<T>
{
private:
    Link<T> *head,*tail;//头尾指针
    Link<T> *setPos(const int i)//第i个指针
    {
        int count = 0;
        // i=1表示定位到头指针
        if( i == -1)
        {
            return head;
        }
        // 头指针指向的节点
        Link<T> *p = head->next;
        while(p!=NULL&&count<i)
        {
            p = p->next;
            count++;
        }
        return p;
    }
public:
    lnkList(int s);
    ~lnkList();
    bool isEmpty()//判断链表是否为空
    {
        if(head->next == NULL)
            return true;
        else
            return false;
    }
    void clear();//将链表存储的内容清空，成为空表
    int length()//返回当前链表的长度
    {
        int count = 0;
        if(head->next == NULL)
        {
            count = 0;
            return count;
        }
        else
        {
            while(head->next == NULL)
            {
                count++;
            }
        }
        return count;

    }
    bool append(const T value)//表为添加一个元素value
    {
        if(tail != 0)
        {
            tail->next = new Link<T>(value,);
            tail = tail->next;
        }
    }

    bool insert(const int i,const T value)//位置i上插入一个元素
    {
        Link<T> *p,*q;
        // 判断插入位置i的前驱节点是不是空
        if((p=setPos(i-1)) == NULL)
        {
            cout<<"非法插入节点"<<endl;
            return false;
        }
        q = new Link<T>(value,p->next);
        p->next = q;
        if(p == tail)//如果插在链尾部
            tail = q;
        return true;
    }
    bool Delete(const int i)//删除位置p上的元素，表的长度减1
    {
        Link<T> *p,*q;
        // 待删节点不存在，即给定的i大于当前链中元素个素
        if((p = setPos(i-1)) == NULL||p == tail)
        {
            cout<<"非法删除节点"<<endl;
            return false;
        }
        // q是真正待删除的节点
        q = p->next;
        if(q == tail)
        {
            tail = p;//待删除节点为尾节点，则修改尾指针
            p->next = NULL:
        }
        else
        {
            p->next = q->next;
            delete q;
            return true;
        }
    }
    bool getValue(const int p,T&value);//返回位置p的元素值
    bool getPos(int &p,const T value);//查找值为value的元素

};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}